/*-------------------------------------------------------------------------
 *
 * freelist.c
 *	  用于管理缓冲池替换策略的例程。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/storage/buffer/freelist.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "port/atomics.h"
#include "storage/buf_internals.h"
#include "storage/bufmgr.h"
#include "storage/proc.h"

#define INT_ACCESS_ONCE(var)	((int)(*((volatile int *)&(var))))


/*
 * 共享的空闲列表控制信息。
 */
typedef struct
{
	/* 自旋锁：保护以下值 */
	slock_t		buffer_strategy_lock;

	/*
	 * 时钟扫描指针：下一个待获取的缓冲区的索引。请注意
	 * 这不是一个具体的缓冲区 - 我们只会增加该值。因此，要
	 * 获取实际缓冲区，需要对 NBuffers 取模。
	 */
	pg_atomic_uint32 nextVictimBuffer;

	int			firstFreeBuffer;	/* 未使用缓冲区的列表头 */
	int			lastFreeBuffer; /* 未使用缓冲区的列表尾 */

	/*
	 * 注意：当 firstFreeBuffer 为 -1（即列表为空）时，lastFreeBuffer 是未定义的
	 */

	/*
	 * 统计信息。这些计数器的宽度应该足够，以至于在单个 bgwriter 循环中不会
	 * 发生溢出。
	 */
	uint32		completePasses; /* 时钟扫描的完整周期 */
	pg_atomic_uint32 numBufferAllocs;	/* 自上次重置以来分配的缓冲区 */

	/*
	 * 在活动时通知的 Bgworker 进程，如果没有则为 -1。见
	 * StrategyNotifyBgWriter。
	 */
	int			bgwprocno;
} BufferStrategyControl;

/* 指向共享状态的指针 */
static BufferStrategyControl *StrategyControl = NULL;

/*
 * 管理共享缓冲区环的私有（非共享）状态以重新使用。
 * 这目前是唯一类型的 BufferAccessStrategy 对象，但将来
 * 我们可能会有更多种类。
 */
typedef struct BufferAccessStrategyData
{
	/* 总体策略类型 */
	BufferAccessStrategyType btype;
	/* buffers[] 数组中的元素数量 */
	int			ring_size;

	/*
	 * 环中“当前”插槽的索引，即最近由 GetBufferFromRing
	 * 返回的插槽。
	 */
	int			current;

	/*
	 * 如果刚刚由 StrategyGetBuffer 返回的缓冲区已经在环中，则为真。
	 */
	bool		current_was_in_ring;

	/*
	 * 缓冲区编号的数组。无效缓冲区（即零）表示我们
	 * 尚未为该环插槽选择缓冲区。为了便于分配，这与
	 * 结构的固定字段一起进行 palloc。
	 */
	Buffer		buffers[FLEXIBLE_ARRAY_MEMBER];
}			BufferAccessStrategyData;


/* 内部函数的原型 */
static BufferDesc *fc_GetBufferFromRing(BufferAccessStrategy fc_strategy,
									 uint32 *fc_buf_state);
static void fc_AddBufferToRing(BufferAccessStrategy fc_strategy,
							BufferDesc *fc_buf);

/*
 * ClockSweepTick - StrategyGetBuffer() 的辅助例程
 *
 * 将时钟指针向前移动一个缓冲区并返回现在位于指针下的
 * 缓冲区的 ID。
 */
static inline uint32 fc_ClockSweepTick(void)
{
	uint32		fc_victim;

	/*
	 * 原子地向前移动指针一个缓冲区 - 如果有多个进程
	 * 这样做，这可能导致缓冲区的返回顺序略有不同。
	 */
	fc_victim =
		pg_atomic_fetch_add_u32(&StrategyControl->nextVictimBuffer, 1);

	if (fc_victim >= NBuffers)
	{
		uint32		fc_originalVictim = fc_victim;

		/* 始终包装我们在 BufferDescriptors 中查找的内容 */
		fc_victim = fc_victim % NBuffers;

		/*
		 * 如果我们是导致环绕的那个，在持有自旋锁时强制
		 * 增加 completePasses。我们需要自旋锁，以便
		 * StrategySyncStart() 能够返回包含 nextVictimBuffer 和
		 * completePasses 的一致值。
		 */
		if (fc_victim == 0)
		{
			uint32		fc_expected;
			uint32		fc_wrapped;
			bool		fc_success = false;

			fc_expected = fc_originalVictim + 1;

			while (!fc_success)
			{
				/*
				 * 在增加 completePasses 时获取自旋锁。这
				 * 允许其他读取者以一致的方式读取 nextVictimBuffer 和
				 * completePasses，这对于 StrategySyncStart() 是必要的。
				 * 理论上，延迟增量可能导致 nextVictimBuffers 的溢出，
				 * 但这极不可能，并且不会造成特别的危害。
				 */
				SpinLockAcquire(&StrategyControl->buffer_strategy_lock);

				fc_wrapped = fc_expected % NBuffers;

				fc_success = pg_atomic_compare_exchange_u32(&StrategyControl->nextVictimBuffer,
														 &fc_expected, fc_wrapped);
				if (fc_success)
					StrategyControl->completePasses++;
				SpinLockRelease(&StrategyControl->buffer_strategy_lock);
			}
		}
	}
	return fc_victim;
}

/*
 * have_free_buffer -- 一种无锁检查，查看缓冲池中是否有空闲缓冲区。
 *
 * 如果结果为真，则一旦空闲缓冲区被其他操作移出，这将变得过时，
 * 因此严格希望使用空闲缓冲区的调用者不应调用此函数。
 */
bool have_free_buffer(void)
{
	if (StrategyControl->firstFreeBuffer >= 0)
		return true;
	else
		return false;
}

/*
 * StrategyGetBuffer
 *
 *	由 bufmgr 调用以获取在 BufferAlloc() 中使用的下一个候选缓冲区。
 *	BufferAlloc() 的唯一严格要求是所选缓冲区当前不能被任何人固定。
 *
 *	strategy 是 BufferAccessStrategy 对象，或者为 NULL 表示默认策略。
 *
 *	为了确保没有其他进程可以在我们之前固定缓冲区，
 *	我们必须在持有缓冲区头自旋锁的同时返回缓冲区。
 */
BufferDesc *
StrategyGetBuffer(BufferAccessStrategy fc_strategy, uint32 *fc_buf_state)
{
	BufferDesc *fc_buf;
	int			fc_bgwprocno;
	int			fc_trycounter;
	uint32		fc_local_buf_state;	/* 为了避免重复（去）引用 */

	/*
	 * 如果给定策略对象，查看它是否可以选择缓冲区。
	 * 我们假设策略对象不需要 buffer_strategy_lock。
	 */
	if (fc_strategy != NULL)
	{
		fc_buf = fc_GetBufferFromRing(fc_strategy, fc_buf_state);
		if (fc_buf != NULL)
			return fc_buf;
	}

	/*
	 * 如果需要，我们需要唤醒 bgwriter。由于我们不想依赖
	 * 自旋锁，因此我们强制从共享内存读取一次，然后
	 * 根据该值设置闩锁。我们需要经过这个过程
	 * 因为否则在我们检查时，bgwprocno 可能会被重置，
	 * 因为编译器可能会重新从内存中读取。
	 *
	 * 如果 bgwriter 在错误的时刻死掉，这可能会设置错误进程的闩锁。
	 * 但由于 PGPROC->procLatch 永远不会被释放，这最糟糕的结果是
	 * 我们设置了某个任意进程的闩锁。
	 */
	fc_bgwprocno = INT_ACCESS_ONCE(StrategyControl->bgwprocno);
	if (fc_bgwprocno != -1)
	{
		/* 先重置 bgwprocno，然后再设置闩锁 */
		StrategyControl->bgwprocno = -1;

		/*
		 * 在这里不获取 ProcArrayLock 有点不妥。但实际上没问题，因为 procLatch 从未被释放，所以我们可能只是设置了错误进程（或没有进程）的 latch。
		 */
		SetLatch(&ProcGlobal->allProcs[fc_bgwprocno].procLatch);
	}

	/*
	 * 我们计算缓冲区分配请求，以便 bgwriter 可以估算缓冲区消耗的速度。请注意，由策略对象回收的缓冲区在这里故意不被计算。
	 */
	pg_atomic_fetch_add_u32(&StrategyControl->numBufferAllocs, 1);

	/*
	 * 首先检查是否有缓冲区在空闲列表中，而不获取锁。由于在每次调用 StrategyGetBuffer() 期间我们不需要检查自旋锁，因此在这里获取它是令人遗憾的——在大多数情况下是无用的。显然这留下了一个竞争条件，即缓冲区被放置在空闲列表中，但我们还没有看到存储 - 但这基本上是无害的，它将在下次缓冲区获取期间被使用。
	 *
	 * 如果空闲列表中有缓冲区，获取自旋锁以弹出一个缓冲区。然后检查该缓冲区是否可用，如果不可用则重复。
	 *
	 * 请注意，freeNext 字段被认为由 buffer_strategy_lock 保护，而不是单个缓冲区自旋锁，因此在不持有自旋锁的情况下操作它们是可以的。
	 */
	if (StrategyControl->firstFreeBuffer >= 0)
	{
		while (true)
		{
			/* 获取自旋锁以从空闲列表中删除元素 */
			SpinLockAcquire(&StrategyControl->buffer_strategy_lock);

			if (StrategyControl->firstFreeBuffer < 0)
			{
				SpinLockRelease(&StrategyControl->buffer_strategy_lock);
				break;
			}

			fc_buf = GetBufferDescriptor(StrategyControl->firstFreeBuffer);
			Assert(fc_buf->freeNext != FREENEXT_NOT_IN_LIST);

			/* 无条件地从空闲列表中删除缓冲区 */
			StrategyControl->firstFreeBuffer = fc_buf->freeNext;
			fc_buf->freeNext = FREENEXT_NOT_IN_LIST;

			/*
			 * 释放锁，以便其他人可以在我们检查此缓冲区时访问空闲列表。
			 */
			SpinLockRelease(&StrategyControl->buffer_strategy_lock);

			/*
			 * 如果缓冲区被固定或使用计数非零，我们无法使用它；丢弃并重试。（这只能发生在 VACUUM 将有效的缓冲区放入空闲列表中，然后其他人在我们到达之前使用了它。这在 8.3 版本后可能根本不可能，但我们最好还是检查一下。）
			 */
			fc_local_buf_state = LockBufHdr(fc_buf);
			if (BUF_STATE_GET_REFCOUNT(fc_local_buf_state) == 0
				&& BUF_STATE_GET_USAGECOUNT(fc_local_buf_state) == 0)
			{
				if (fc_strategy != NULL)
					fc_AddBufferToRing(fc_strategy, fc_buf);
				*fc_buf_state = fc_local_buf_state;
				return fc_buf;
			}
			UnlockBufHdr(fc_buf, fc_local_buf_state);
		}
	}

	/* 空闲列表中没有缓冲区，因此运行“时钟扫描”算法 */
	fc_trycounter = NBuffers;
	for (;;)
	{
		fc_buf = GetBufferDescriptor(fc_ClockSweepTick());

		/*
		 * 如果缓冲区被固定或使用计数非零，我们无法使用它；递减使用计数（除非被固定）并继续扫描。
		 */
		fc_local_buf_state = LockBufHdr(fc_buf);

		if (BUF_STATE_GET_REFCOUNT(fc_local_buf_state) == 0)
		{
			if (BUF_STATE_GET_USAGECOUNT(fc_local_buf_state) != 0)
			{
				fc_local_buf_state -= BUF_USAGECOUNT_ONE;

				fc_trycounter = NBuffers;
			}
			else
			{
				/* 找到了可用的缓冲区 */
				if (fc_strategy != NULL)
					fc_AddBufferToRing(fc_strategy, fc_buf);
				*fc_buf_state = fc_local_buf_state;
				return fc_buf;
			}
		}
		else if (--fc_trycounter == 0)
		{
			/*
			 * 我们扫描了所有缓冲区而没有进行任何状态更改，因此所有缓冲区都是被固定的（或在我们查看时是被固定的）。我们可以希望最终会有人释放一个缓冲区，但风险被卡在无限循环中可能更糟。
			 */
			UnlockBufHdr(fc_buf, fc_local_buf_state);
			elog(ERROR, "no unpinned buffers available");
		}
		UnlockBufHdr(fc_buf, fc_local_buf_state);
	}
}

/*
 * StrategyFreeBuffer: 将缓冲区放入空闲列表
 */
void StrategyFreeBuffer(BufferDesc *fc_buf)
{
	SpinLockAcquire(&StrategyControl->buffer_strategy_lock);

	/*
	 * 可能我们被告知将某个东西放入空闲列表，而它已经在其中；如果是这样，不要搞乱列表。
	 */
	if (fc_buf->freeNext == FREENEXT_NOT_IN_LIST)
	{
		fc_buf->freeNext = StrategyControl->firstFreeBuffer;
		if (fc_buf->freeNext < 0)
			StrategyControl->lastFreeBuffer = fc_buf->buf_id;
		StrategyControl->firstFreeBuffer = fc_buf->buf_id;
	}

	SpinLockRelease(&StrategyControl->buffer_strategy_lock);
}

/*
 * StrategySyncStart -- 告诉 BgBufferSync 从哪里开始同步
 *
 * 结果是最先同步的缓冲区的缓冲区索引。
 * BgBufferSync() 将从那里开始循环遍历缓冲区数组。
 *
 * 此外，如果传入非 NULL 指针，我们还返回完成通行计数（实际上是 nextVictimBuffer 的高位）和最近的缓冲区分配计数。分配计数在读取后被重置。
 */
int StrategySyncStart(uint32 *fc_complete_passes, uint32 *fc_num_buf_alloc)
{
	uint32		fc_nextVictimBuffer;
	int			fc_result;

	SpinLockAcquire(&StrategyControl->buffer_strategy_lock);
	fc_nextVictimBuffer = pg_atomic_read_u32(&StrategyControl->nextVictimBuffer);
	fc_result = fc_nextVictimBuffer % NBuffers;

	if (fc_complete_passes)
	{
		*fc_complete_passes = StrategyControl->completePasses;

		/*
		 * 另外添加在完全通行计数之前发生的包装次数。参见 ClockSweepTick()。
		 */
		*fc_complete_passes += fc_nextVictimBuffer / NBuffers;
	}

	if (fc_num_buf_alloc)
	{
		*fc_num_buf_alloc = pg_atomic_exchange_u32(&StrategyControl->numBufferAllocs, 0);
	}
	SpinLockRelease(&StrategyControl->buffer_strategy_lock);
	return fc_result;
}

/*
 * StrategyNotifyBgWriter -- 设置或清除分配通知 latch
 *
 * 如果 bgwprocno 不是 -1，则下一次调用 StrategyGetBuffer 将设置该 latch。传入 -1 以在发生之前清除待处理的通知。此功能供 bgwriter 进程用于唤醒自己，而不是供其他人使用。
 */
void StrategyNotifyBgWriter(int fc_bgwprocno)
{
	/*
	 * 我们获取 buffer_strategy_lock 只是为了确保存储对 StrategyGetBuffer 来说是原子性的。bgwriter 应该很少调用此功能，因此在安全的情况下不会产生性能损失。
	 */
	SpinLockAcquire(&StrategyControl->buffer_strategy_lock);
	StrategyControl->bgwprocno = fc_bgwprocno;
	SpinLockRelease(&StrategyControl->buffer_strategy_lock);
}


/*
 * StrategyShmemSize
 *
 * 估算由空闲列表相关结构使用的共享内存大小。
 *
 * 注意：由于某些历史原因，缓冲区查找哈希表的大小也在这里确定。
 */
Size StrategyShmemSize(void)
{
	Size		fc_size = 0;

	/* 查找哈希表的大小 ... 请参见 StrategyInitialize 中的注释 */
	fc_size = add_size(fc_size, BufTableShmemSize(NBuffers + NUM_BUFFER_PARTITIONS));

	/* 共享替换策略控制块的大小 */
	fc_size = add_size(fc_size, MAXALIGN(sizeof(BufferStrategyControl)));

	return fc_size;
}

/*
 * StrategyInitialize -- 初始化缓冲区缓存替换
 *		策略。
 *
 * 假设：所有缓冲区已经构建成一个链表。
 *		仅由 postmaster 调用，并且仅在初始化期间。
 */
void StrategyInitialize(bool fc_init)
{
	bool		fc_found;

	/*
	 * 初始化共享缓冲区查找哈希表。
	 *
	 * 由于我们无法容忍耗尽查找表条目，因此我们必须确保在这里指定足够的表大小。最大稳定状态用法当然是 NBuffers 条目，但是 BufferAlloc() 尝试在删除旧条目之前插入新条目。从原则上讲，这可能会在每个分区同时发生，因此我们可能需要多达 NBuffers + NUM_BUFFER_PARTITIONS 条目。
	 */
	InitBufTable(NBuffers + NUM_BUFFER_PARTITIONS);

	
/*
	 * 获取或创建共享策略控制块
	 */
	StrategyControl = (BufferStrategyControl *)
		ShmemInitStruct("Buffer Strategy Status",
						sizeof(BufferStrategyControl),
						&fc_found);

	if (!fc_found)
	{
		/*
		 * 通常只执行一次，通常在 postmaster 中
		 */
		Assert(fc_init);

		SpinLockInit(&StrategyControl->buffer_strategy_lock);

		/*
		 * 获取我们策略的整个空闲缓冲区链表。我们假设它之前已由 InitBufferPool() 设置。
		 */
		StrategyControl->firstFreeBuffer = 0;
		StrategyControl->lastFreeBuffer = NBuffers - 1;

		/* 初始化时钟扫描指针 */
		pg_atomic_init_u32(&StrategyControl->nextVictimBuffer, 0);

		/* 清除统计信息 */
		StrategyControl->completePasses = 0;
		pg_atomic_init_u32(&StrategyControl->numBufferAllocs, 0);

		/* 没有待处理的通知 */
		StrategyControl->bgwprocno = -1;
	}
	else
		Assert(!fc_init);
}


/* ----------------------------------------------------------------
 *				后端私有缓冲区环管理
 * ----------------------------------------------------------------
 */


/*
 * GetAccessStrategy -- 创建 BufferAccessStrategy 对象
 *
 * 对象在当前内存上下文中分配。
 */
BufferAccessStrategy
GetAccessStrategy(BufferAccessStrategyType fc_btype)
{
	BufferAccessStrategy fc_strategy;
	int			fc_ring_size;

	/*
	 * 选择要使用的环的大小。有关合理性的说明，请参见 buffer/README。
	 *
	 * 注意：如果您更改 BAS_BULKREAD 的环大小，请同时查看
	 * access/heap/syncscan.c 中的 SYNC_SCAN_REPORT_INTERVAL。
	 */
	switch (fc_btype)
	{
		case BAS_NORMAL:
			/* 如果有人请求 NORMAL，就给他们一个 "default" 对象 */
			return NULL;

		case BAS_BULKREAD:
			fc_ring_size = 256 * 1024 / BLCKSZ;
			break;
		case BAS_BULKWRITE:
			fc_ring_size = 16 * 1024 * 1024 / BLCKSZ;
			break;
		case BAS_VACUUM:
			fc_ring_size = 256 * 1024 / BLCKSZ;
			break;

		default:
			elog(ERROR, "unrecognized buffer access strategy: %d",
				 (int) fc_btype);
			return NULL;		/* 保持编译器安静 */
	}

	/* 确保环不会占用共享缓冲区过大比例 */
	fc_ring_size = Min(NBuffers / 8, fc_ring_size);

	/* 分配对象并将所有元素初始化为零 */
	fc_strategy = (BufferAccessStrategy)
		palloc0(offsetof(BufferAccessStrategyData, buffers) +
				fc_ring_size * sizeof(Buffer));

	/* 设置未以零开头的字段 */
	fc_strategy->btype = fc_btype;
	fc_strategy->ring_size = fc_ring_size;

	return fc_strategy;
}

/*
 * FreeAccessStrategy -- 释放一个 BufferAccessStrategy 对象
 *
 * 现在简单的 pfree 就可以了，但我们希望调用方
 * 不要对 BufferAccessStrategy 的表示做出太多假设。
 */
void FreeAccessStrategy(BufferAccessStrategy fc_strategy)
{
	/* 如果在 "default" 策略上调用，就不要崩溃 */
	if (fc_strategy != NULL)
		pfree(fc_strategy);
}

/*
 * GetBufferFromRing -- 从环中返回一个缓冲区，如果环
 *		为空则返回 NULL。
 *
 * 返回的缓冲区上持有 bufhdr 自旋锁。
 */
static BufferDesc *
fc_GetBufferFromRing(BufferAccessStrategy fc_strategy, uint32 *fc_buf_state)
{
	BufferDesc *fc_buf;
	Buffer		fc_bufnum;
	uint32		fc_local_buf_state;	/* 为了避免重复（去）引用 */


	/* 前进到下一个环槽 */
	if (++fc_strategy->current >= fc_strategy->ring_size)
		fc_strategy->current = 0;

	/*
	 * 如果槽尚未填充，请告诉调用方使用正常的分配策略分配新缓冲区。
	 * 然后他将通过调用 AddBufferToRing 来填充这个槽。
	 */
	fc_bufnum = fc_strategy->buffers[fc_strategy->current];
	if (fc_bufnum == InvalidBuffer)
	{
		fc_strategy->current_was_in_ring = false;
		return NULL;
	}

	/*
	 * 如果缓冲区被固定，我们在任何情况下都无法使用它。
	 *
	 * 如果 usage_count 为 0 或 1，那缓冲区就是可用的（我们期望是 1，
	 * 因为我们自己之前对环元素的使用会将其保留在那里，但可能由于时钟清扫而减少）。
	 * 更高的 usage_count 表示其他人已接触缓冲区，因此我们
	 * 不应重新使用它。
	 */
	fc_buf = GetBufferDescriptor(fc_bufnum - 1);
	fc_local_buf_state = LockBufHdr(fc_buf);
	if (BUF_STATE_GET_REFCOUNT(fc_local_buf_state) == 0
		&& BUF_STATE_GET_USAGECOUNT(fc_local_buf_state) <= 1)
	{
		fc_strategy->current_was_in_ring = true;
		*fc_buf_state = fc_local_buf_state;
		return fc_buf;
	}
	UnlockBufHdr(fc_buf, fc_local_buf_state);

	/*
	 * 告诉调用方使用正常的分配策略分配新缓冲区。
	 * 他将通过 AddBufferToRing 替换该环元素。
	 */
	fc_strategy->current_was_in_ring = false;
	return NULL;
}

/*
 * AddBufferToRing -- 将缓冲区添加到缓冲区环
 *
 * 调用方必须在缓冲区上持有缓冲区头自旋锁。由于在持有自旋锁时调用，
 * 因此这个过程应该非常便宜。
 */
static void fc_AddBufferToRing(BufferAccessStrategy fc_strategy, BufferDesc *fc_buf)
{
	fc_strategy->buffers[fc_strategy->current] = BufferDescriptorGetBuffer(fc_buf);
}

/*
 * StrategyRejectBuffer -- 考虑拒绝一个脏缓冲区
 *
 * 当使用非默认策略时，如果 StrategyGetBuffer 选中的缓冲区需要
 * 被写出，并且执行此操作还需要刷新 WAL，缓冲区管理器会调用此函数。
 * 这让我们有机会选择不同的牺牲品。
 *
 * 如果缓冲区管理器应该请求一个新牺牲品则返回 true，如果此缓冲区
 * 应该被写出并重新使用则返回 false。
 */
bool StrategyRejectBuffer(BufferAccessStrategy fc_strategy, BufferDesc *fc_buf)
{
	/* 我们仅在 bulkread 模式下执行此操作 */
	if (fc_strategy->btype != BAS_BULKREAD)
		return false;

	/* 不要干扰正常缓冲区替换策略的行为 */
	if (!fc_strategy->current_was_in_ring ||
		fc_strategy->buffers[fc_strategy->current] != BufferDescriptorGetBuffer(fc_buf))
		return false;

	/*
	 * 从环中移除脏缓冲区；这是必要的，以防止所有环成员都为脏时出现无限
	 * 循环。
	 */
	fc_strategy->buffers[fc_strategy->current] = InvalidBuffer;

	return true;
}
